package com.maxlong.study.tree;

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * @author 作者 maxlong:
 * @version 创建时间：2018-03-07 0007 9:38
 * 类说明
 */
public class SolutionTree {

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode10 = new TreeNode(10);


        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;

        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;

        treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;

        treeNode4.left = treeNode8;
        treeNode4.right = treeNode9;

        treeNode9.right = treeNode10;

        printTreeLevel(treeNode1);
        printTreeLevel2(treeNode1);

    }

    /**
     * 从左到右按层打印二叉树
     *
     * @param root
     */
    private static void printTreeLevel(TreeNode root) {

        Queue<TreeNode> queue = new ArrayBlockingQueue<>(100);

        queue.add(root);

        TreeNode last = root;
        TreeNode nlast = null;

        while (queue.size() != 0) {

            TreeNode out = queue.poll();
            System.out.print(out.val + " ");

            if (out.left != null) {
                queue.add(out.left);
                nlast = out.left;
            }

            if (out.right != null) {
                queue.add(out.right);
                nlast = out.right;
            }

            if (out == last) {
                System.out.println();
                last = nlast;
            }

        }

    }

    /**
     * 先从左到右，后从右到左，放入数组中
     * @param root
     */
    private static void printTreeLevel2(TreeNode root) {

        List<List<Integer>> order = new ArrayList<>();

        Queue<TreeNode> queue = new ArrayBlockingQueue<>(100);

        queue.add(root);

        TreeNode last = root;
        TreeNode nLast = null;
        boolean leftToRight = true;

        List<Integer> list = new ArrayList<>();

        while (queue.size() != 0) {

            TreeNode out = queue.poll();
            list.add(out.val);

            if (out.left != null) {
                queue.add(out.left);
                nLast = out.left;
            }

            if (out.right != null) {
                queue.add(out.right);
                nLast = out.right;
            }

            if (out == last) {
                if (!leftToRight) {
                    Collections.reverse(list);
                }
                order.add(list);
                list = new ArrayList<>();
                last = nLast;
                leftToRight = !leftToRight;
            }

        }

        System.out.println(order);

    }


}